{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Arbres Couvrants Minimaux\n",
    "\n",
    "Dans ce DM, on va regarder comment trouver un arbre couvrant minimal d'un graphe, et utiliser cet algorithme pour générer des labyrinthes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from matplotlib.collections import LineCollection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algorithme de Kruskal\n",
    "\n",
    "L'algorithme de Kruskal permet de trouver efficacement un arbre couvrant minimal.\n",
    "\n",
    "L'idée de cet algorithme est de construire un arbre qui passe par tous les sommets.\n",
    "Pour cela, au début, on considère que chaque sommet constitue à lui tout seul un arbre.\n",
    "\n",
    "On a donc un dictionnaire `ensemble` qui, pour chaque sommet, donne le numéro de l'ensemble auquel il appartient.\n",
    "Au début, on a autant d'ensembles que de sommet, et chaque sommet est dans un ensemble numéroté `i`.\n",
    "\n",
    "Ensuite, on trie les arêtes par poids, et on itère sur les arêtes, en commençant par celle de poids minimal.\n",
    "Pour chacune de ces arêtes :\n",
    "    * si les deux sommets sont dans le même ensemble, on ignore l'arête (les deux sommets sont déjà reliés, donc on n'a pas besoin de rajouter une arête pour les relier) ;\n",
    "    * si les deux sommets sont dans des ensembles différents :\n",
    "        * on fusionne les deux ensembles. C'est à dire que si le sommet 1 est dans l'ensemble numéro `i` et le sommet 2 dans l'ensemble numéro `j`, on change tous les `j` en `i` : dès lors, tous les sommets reliés à un des deux sommets de l'arête sont dans le même ensemble `i` ;\n",
    "        * on rajoute l'arête dans la liste des arêtes de l'arbre.\n",
    "\n",
    "Sous forme de pseudo code :\n",
    "\n",
    "* `aretes_arbre = []` ;\n",
    "* `ensemble = {u: i for i, u in enumerate(G.nodes())}` ;\n",
    "* `aretes_triees = arêtes de G triées par poids croissant` ;\n",
    "* pour chaque arête `arete` dans `aretes_triees` (dans l'ordre) :\n",
    "    * `(sommet1, sommet2) = aretes` ;\n",
    "    * si `ensemble[sommet1]` et `ensemble[sommet2]` sont égaux : on ne fait rien ;\n",
    "    * si `ensemble[sommet1]` et `ensemble[sommet2]` sont différents :\n",
    "        * pour tous les sommets tels que `ensemble[sommet] == ensemble[sommet2]`, redéfinir `ensemble[sommet1]` avec la valeur de `ensemble[sommet2]`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question.** Implémentez l'algorithme de Kruskal et faites le tourner sur un graphe pour vérifier que vous trouvez bien un arbre couvrant minimal. Il prendra en entrée un graphe (`nx.Graph`) et renverra en sortie un graphe (`nx.Graph`) qui correspond à l'arbre couvrant minimal."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def kruskal(G, afficher=True):\n",
    "    # implémentez la fonction ici"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voilà du code pour tester votre algorithme :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rng=np.random.default_rng(seed=12)\n",
    "G = nx.fast_gnp_random_graph(10, 0.3, seed=12)\n",
    "pos = nx.spring_layout(G, seed=123)\n",
    "\n",
    "weights = {(u, v): int(rng.random() * 100) for (u, v) in G.edges()}\n",
    "nx.set_edge_attributes(G, values=weights, name='weight')\n",
    "\n",
    "G_tree = kruskal(G)\n",
    "\n",
    "nx.draw(G, pos)\n",
    "nx.draw(G, pos,\n",
    "        node_color=\"pink\", \n",
    "        edgecolors=\"black\", node_size=500)\n",
    "nx.draw(G_tree, pos,\n",
    "        node_color=\"pink\",\n",
    "        edge_color=\"red\", width=4,\n",
    "        edgecolors=\"black\", node_size=500)\n",
    "nx.draw_networkx_edge_labels(G, pos, edge_labels=weights)\n",
    "\n",
    "plt.savefig(\"images/grid_span_tree.pdf\")\n",
    "plt.show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Application aux labyrinthes\n",
    "\n",
    "On peut facilement utiliser cet algorithme pour créer des labyrinthes : on crée un graphe qui consiste en une grille de la taille de notre labyrinthe, puis on cherche un arbre couvrant de ce graphe.\n",
    "\n",
    "Pour donner un caractère aléatoire au labyrinthe généré, on peut donner des poids aléatoires aux arêtes : ainsi, l'arbre couvrant minimal trouvé dépendra de la génération de ces poids, ce qui donne donc un arbre différent à chaque fois !\n",
    "\n",
    "On représentera en mémoire un labyrinthe comme un graphe : les sommets sont les cases du labyrinthes, et il y a une arête entre deux sommets si il est possible de passer d'une case à l'autre (ie. il n'y a pas de mur entre les deux).\n",
    "\n",
    "Pour afficher votre labyrinthe, vous pourrez utiliser cette fonction :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# affichage du labyrinthe\n",
    "def afficher_labyrinthe(lab, solution=None, explored=None):\n",
    "    pos = {u: u for u in lab.nodes()}\n",
    "    width, height = (1 + list(lab.nodes())[-1][0], 1 + list(lab.nodes())[-1][1]) \n",
    "    \n",
    "    plt.figure(figsize=(width, height))\n",
    "    lines = [[(-0.5, -0.5), (width - 0.5, - 0.5)],\n",
    "             [(-0.5, -0.5), (- 0.5, height - 0.5)],\n",
    "             [(width - 0.5, -0.5), (width - 0.5, height - 0.5)],\n",
    "             [(-0.5, height - 0.5), (width - 0.5, height - 0.5)]]\n",
    "    \n",
    "    for i in range(width):\n",
    "        for j in range(height):\n",
    "            if ((i, j), (i, j+1)) not in lab.edges():\n",
    "                lines.append([(i - 0.5, j + 0.5), (i + 0.5, j + 0.5)])\n",
    "            if ((i, j), (i+1, j)) not in lab.edges():\n",
    "                lines.append([(i + 0.5, j - 0.5), (i + 0.5, j + 0.5)])\n",
    "    \n",
    "    if solution is not None:\n",
    "        solx = [u for (u, v) in solution]\n",
    "        soly = [v for (u, v) in solution]\n",
    "        plt.plot(solx, soly, color=\"red\")\n",
    "        \n",
    "    if explored is not None:\n",
    "        explx = [u for (u, v) in explored]\n",
    "        exply = [v for (u, v) in explored]\n",
    "        plt.scatter(explx, exply)\n",
    "    \n",
    "    plt.xlim(-0.5, width-0.5)\n",
    "    plt.ylim(-0.5, height-0.5)\n",
    "    plt.gca().add_collection(LineCollection(lines, colors=\"black\"))\n",
    "    plt.axis(\"off\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question.** Utiliser l'algorithme `kruskal` implémenté au dessus pour générer un labyrinthe."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def labyrinthe(dimension=(10, 10)):\n",
    "    # implémentez la fonction ici"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question.** Affichez votre labyrinthe !"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}